package 剑指II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-25
 **/

public class Jz083没有重复元素集合的全排列 {

    /**
     * 给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     * 示例 2：
     * 输入：nums = [0,1]
     * 输出：[[0,1],[1,0]]
     * 示例 3：
     * 输入：nums = [1]
     * 输出：[[1]]
     * 提示：
     * 1 <= nums.length <= 6
     * -10 <= nums[i] <= 10
     * nums 中的所有整数 互不相同
     *  
     * 注意：本题与主站 46 题相同：https://leetcode-cn.com/problems/permutations/ 
     */

    private List<List<Integer>> result = new ArrayList<>();
    private int target;

    public List<List<Integer>> permute(int[] nums, int target) {
        this.target = target;
        Arrays.sort(nums);
        this.dfs(nums, 0, 0, new ArrayList<>());
        return this.result;
    }

    private void dfs(int[] arr, int index, int sum, List<Integer> path) {
        if (sum == this.target) {
            this.result.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < arr.length; i++) {
            if (sum + arr[i] > this.target) {
                continue;
            }
            path.add(arr[i]);
            this.dfs(arr, i + 1, sum + arr[i], path);
            path.remove(path.size() - 1);
        }
    }

}
